class Solution {
public:
    vector<int> finalPrices(vector<int>& prices)
    {
        int n = prices.size();
        stack<int> st;
        vector<int> ret(n);
        for (int i = 0; i < n; i++)
        {
            int t = prices[i];
            while (st.size() && t <= prices[st.top()])
            {
                int x = st.top();
                st.pop();
                ret[x] = prices[x] - t;
            }
            st.push(i);
        }
        while (st.size())
        {
            int x = st.top();
            st.pop();
            ret[x] = prices[x];
        }
        return ret;
    }
};